package dichotomy.find.peak.element;
/**
 * @Time 2020/1/12
 * @author 王光浩
 * @Need 给定一个数组，找出其中的峰值元素，峰值元素指的是该元素大于相邻的左右两边元素值。
 * @Thinking 使用二分法
 *           思路：使用while循环找出其中符合条件的target下标，循环结束的条件是later<previous,循环体的内容
 *                 为比较mid下标所在的元素值与两边元素值的大小，如果左边大于当前下标所在的元素则将later=mid-1；
 *                 如果右边大于当前下标所在元素则将previous=mid+1（优先级为先判断左边），否则返回mid所在的下标。
 *           复杂度分析：时间复杂度O（logn），空间复杂度O（1）
 */
public class MyMethodTwo {
    public int findPeakElement(int[] nums) {
    	int later=nums.length-1;
    	int previous=0;
    	int mid;
    	int len=nums.length;
    	if(nums.length==1)return 0;
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		//注意这里要做边界值的判断，如果mid处在下标为0处和mid处在下标为nums.lenght-1处要进行特殊处理
    		if(mid==0) {
    			if(nums[mid]>nums[mid+1])
    				return mid;
    			else
    				previous=mid+1;
    		}
    		else if(mid==len-1) {
    			if(nums[mid]>nums[mid-1])
    				return mid;
    			else
    				later=mid-1;
    		}
    		else {
    			if(nums[mid]>nums[mid+1] && nums[mid]>nums[mid-1])
    				return mid;
    			else if(nums[mid]<nums[mid+1])
    				previous=mid+1;
    			else
    				later=mid-1;
    		}
    	}
    	return later;
    }
}
